package 链表;

/**
 * ---------------------------------------------------------
 * <h>https://leetcode-cn.com/problems/partition-list/</h>
 * <p>
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 * 示例 1：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 * 示例 2：
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 * 提示：
 * 链表中节点的数目在范围 [0, 200] 内
 * -100 <= Node.val <= 100
 * -200 <= x <= 200
 * </p>
 * Created by Frank on 2021/3/29.
 * <a href="mailto:frankyao10110@gmail.com">Contact me</a>
 * ---------------------------------------------------------
 */
class _分隔链表 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode tail = head;
        tail = tail.next = new ListNode(4);
        tail = tail.next = new ListNode(3);
        tail = tail.next = new ListNode(2);
        tail = tail.next = new ListNode(5);
        tail.next = new ListNode(2);

        ListNode list = partition(head, 3);

        while(list != null) {
            System.out.println("Node: " + list.val);
            list = list.next;
        }
    }
    public static ListNode partition(ListNode head, int x) {
        if (head == null) return null;

        ListNode l1 = new ListNode(0);
        ListNode l2 = new ListNode(0);
        ListNode tail1 = l1;
        ListNode tail2 = l2;

        while (head != null) {
            if (head.val < x) {
                tail1 = tail1.next = head;
            }else {
                tail2 = tail2.next = head;
            }

            head = head.next;
        }
        tail2.next = null;
        tail1.next = l2.next;

        return l1.next;
    }
}
